#ifndef SIMPLE_SUPPORT_ALGORITHM_SET_OPS_HPP
#define SIMPLE_SUPPORT_ALGORITHM_SET_OPS_HPP
#include <algorithm> // std::is_sorted
#include <functional> // std::less
#include <type_traits> // std::is_same_v
#include "../function_utils.hpp" // support::invoke

namespace simple::support
{

	class ignore_count {};

	namespace detail
	{
		template <typename IgnoreCount, typename MinuendIt, typename SubtrahendIt, typename Less>
		constexpr bool not_in_set
		(
			SubtrahendIt& sub_begin, SubtrahendIt sub_end,
			MinuendIt minuend,
			Less&& less
		)
		{
			while(sub_begin != sub_end)
			{
				if(support::invoke(less, *minuend, *sub_begin))
					return true;
				else if(support::invoke(less, *sub_begin, *minuend))
					++sub_begin;
				else
				{
					if constexpr (not std::is_same_v<IgnoreCount, ignore_count>)
						++sub_begin;
					return false;
				}
			}
			return true;
		}
	} // namespace detail

	// cause standard version is not allowed to work in place for some reason
	// also allows ignoring element counts in case of multisets
	template <typename IgnoreCount = void, typename MinuendIt = void, typename SubtrahendIt = void, typename DifferenceIt = void, typename Less = std::less<>>
	constexpr DifferenceIt set_difference
	(
		MinuendIt begin, MinuendIt end,
		SubtrahendIt sub_begin, SubtrahendIt sub_end,
		DifferenceIt diff,
		Less&& less = std::less<>{}
	)
	{
		assert(std::is_sorted(begin, end, less));
		assert(std::is_sorted(sub_begin, sub_end, less));
		while(begin != end)
		{
			if(detail::not_in_set<IgnoreCount>(sub_begin, sub_end, begin, less))
				*diff++ = *begin;
			++begin;
		}
		return diff;
	}

} // namespace simple::support

#endif /* end of include guard */
